// 版权所有2012 Go作者。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package strings

// stringFinder在源文本中高效地查找字符串。它是使用Boyer-Moore字符串搜索算法实现的：
// https:
// https:
// 文档使用基于1的索引）
type stringFinder struct {
	// 模式是我们在文本中搜索的字符串。
	pattern string

	// badCharSkip[b]包含模式
	// 的最后一个字节与模式中最右边出现的b之间的距离。如果b不在模式中，则
	// badCharSkip[b]为len（模式）。
	// 
	// 每当在文本中发现与字节b不匹配时，我们可以安全地将匹配帧至少移动到badCharSkip[b]，直到下次
	// 匹配字符可以对齐为止。
	badCharSkip [256]int

	// goodSuffixSkip[i]定义了给定的
	// 后缀模式[i+1:]匹配的匹配帧的移动距离，但字节模式[i]不匹配。有两种情况需要考虑：
	// 
	// 1。匹配的后缀出现在模式中的其他位置（前面有一个不同的
	// 字节，我们可能会匹配）。在这种情况下，我们可以
	// 移动匹配帧以与下一个后缀块对齐。例如，对于
	// ，模式“mississi”的后缀“issi”位于索引1的下一个
	// （按从右到左的顺序），因此goodSuffixSkip[3]==
	// shift+len（后缀）==3+4==7。中国英语学习网中国英语学习网中国英语学习网中国英语学习网中国英语学习网中国英语学习网中国英语学习网中国英语学习网中国英语学习网中国英语学习网中国英语学习网。如果匹配的后缀没有出现在模式中的其他位置，则匹配帧的部分前缀可能与匹配后缀的结尾共享。在这种情况下，goodSuffixSkip[i]将包含移动帧使前缀的这一部分与后缀
	// 对齐的距离。例如，在模式“abcxxabc”中，当发现从后面开始的第一个
	// 不匹配位于位置3时，在模式的其他位置找不到匹配的
	// 后缀“xxabc”。但是，其最右边的“abc”（位置6）是整个模式的前缀，因此
	// goodSuffixSkip[3]==shift+len（后缀）==6+5==11。
	goodSuffixSkip []int
}

func makeStringFinder(pattern string) *stringFinder {
	f := &stringFinder{
		pattern:        pattern,
		goodSuffixSkip: make([]int, len(pattern)),
	}
	// last是模式中最后一个字符的索引。
	last := len(pattern) - 1

	// 建立坏字符表。
	// 不在模式中的字节可以跳过一个模式的长度。
	for i := range f.badCharSkip {
		f.badCharSkip[i] = len(pattern)
	}
	// 循环条件是<而不是<=因此最后一个字节与自身的距离不是零。如果发现这个字节不合适，则表示它不在最后一个位置。
	for i := 0; i < last; i++ {
		f.badCharSkip[pattern[i]] = last - i
	}

	// 构建好的后缀表。
	// 第一遍：将每个值设置为下一个索引，该索引以
	// 模式的前缀开头。
	lastPrefix := last
	for i := last; i >= 0; i-- {
		if HasPrefix(pattern, pattern[i+1:]) {
			lastPrefix = i + 1
		}
		// lastprifix是移位，而（last-i）是len（后缀）。
		f.goodSuffixSkip[i] = lastPrefix + last - i
	}
	// 第二遍：从前面开始查找重复的图案后缀。
	for i := 0; i < last; i++ {
		lenSuffix := longestCommonSuffix(pattern, pattern[1:i+1])
		if pattern[i-lenSuffix] != pattern[last-lenSuffix] {
			// （last-i）是移位，lenSuffix是len（后缀）。
			f.goodSuffixSkip[last-lenSuffix] = lenSuffix + last - i
		}
	}

	return f
}

func longestCommonSuffix(a, b string) (i int) {
	for ; i < len(a) && i < len(b); i++ {
		if a[len(a)-1-i] != b[len(b)-1-i] {
			break
		}
	}
	return
}

// 下一步返回模式第一次出现时的文本索引。如果找不到模式，则返回-1。
func (f *stringFinder) next(text string) int {
	i := len(f.pattern) - 1
	for i < len(text) {
		// 从结尾向后比较，直到第一个不匹配的字符。
		j := len(f.pattern) - 1
		for j >= 0 && text[i] == f.pattern[j] {
			i--
			j--
		}
		if j < 0 {
			return i + 1 // 匹配
		}
		i += max(f.badCharSkip[text[i]], f.goodSuffixSkip[j])
	}
	return -1
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
